#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import defaultdict


class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @return: The maximum size
    """
    # def backPack(self, room, A):
    #     self.record = defaultdict(dict)
    #     self.A = A
    #     self.room = room

    #     return self.rec_calc(room, len(A)-1)

    # def rec_calc(self, room, idx):
    #     if idx == -1:
    #         return 0

    #     item_size = self.A[idx]
    #     v = self.record[idx].get(room)
    #     if v is not None:
    #         return v

    #     last = self.rec_calc(room, idx-1)
    #     if room < item_size:
    #         size = last
    #     else:
    #         size = max(last, item_size + self.rec_calc(room-item_size, idx-1))
    #         # print(size)

    #     self.record[idx][room] = size
    #     return size

    def backPack(self, m, A):
        self.record = [0] * (m + 1)      # [i]
        self.m = m

        for item_size in A:
            # self.process_item(item_size)
            for room in reversed(range(item_size, self.m+1)):
            # for room in reversed(range(1, item_size+1)):
                # if room < item:
                #     max_value = self.record[]
                contain_value = item_size + self.record[room - item_size]
                non_contain_value = self.record[room]
                self.record[room] = max(contain_value, non_contain_value)

        return self.record[-1]

    def process_item(self, item_size):


def main():
    print("start main")
    s = Solution()
    ret = s.backPack(90, [12,3,7,4,5,13,2,8,4,7,6,5,7])
    # print(s.record[-1])
    print(ret)

if __name__ == "__main__":
    main()
